package no.ffi.gismoidm.utils;
import java.util.*;
/**
 * A threadsafe list. Robust to concurrent accesses. 
 * Implemented as a circular doubly linked list.
 *
 * @author anf
 */
public class ConcurrentArrayList implements java.io.Serializable {
    
    /**
     * Node is the link node structure
     */ 
    class Node implements java.io.Serializable {
        Object o;
        boolean inList; // set to true when node is in list, and to false when it is removed
        Node next,prev;
        public Node(Object o) { this.o=o; next=this; prev=this; inList = true;}
    }
    /** Inner class for iterator operations. The iterator interface is not
     * well suited for concurrent operation, since an element may be
     * inserted or removed between the calls to "hasNext()" and "next()".
     * Thus the "next()"-call may still throw an exception. */
    class Itr implements ConcurrentIterator {
        Node idx;
        public Itr() { idx = listHead;}
        public boolean hasNext() { 
            synchronized (ConcurrentArrayList.this) {
                return (idx.next!=listHead);
            }
        }
        public Object next() {
            synchronized (ConcurrentArrayList.this) {
                idx = idx.next;
                if (idx == listHead) throw new NoSuchElementException();
                return idx.o;
            }
        }
        public void remove() {
            synchronized (ConcurrentArrayList.this) {
//                if (idx == listHead) throw new java.lang.IllegalStateException("Attempt to remove from an empty list");
                if (idx.inList) {
                    idx.next.prev = idx.prev;
                    idx.prev.next = idx.next;
                    idx.inList = false; // never remove same node twice
                    size--;
                }
            }
        }
        
        public Object nextElement() {
            try {
                return next();
            } catch (NoSuchElementException e) { return null; }
        }
    }
    
    Node listHead;
    int size;
    
    public ConcurrentArrayList() {
        listHead = new Node(null);
        listHead.inList = false; // So it is never removed
        size = 0;
    }
    
    public void add(Object a) {
        if (a==null) 
            throw new NullPointerException("Null object not allowed in list");
        Node n = new Node(a);
        synchronized(this) {
            // Insert at the end of the list
            n.prev = listHead.prev;
            n.next = listHead;
            listHead.prev.next = n;
            listHead.prev = n;
            size++;
        }
    }

    /**
     * This operation is TERRIBLY unsafe during a concurrent operation!
     * Other threads may insert or delete elements, moving the object
     * you wish to delete to another index. So you risk deleting
     * the wrong object.
     * Therefore, this method simply throws an UnsupportedOperationException
     */
    public void remove(int i) {
        throw new UnsupportedOperationException("Unsafe concurrent operation");
    }
    
    /** 
     * Remove one object from the list which is equal to o. This operation
     * need to traverse the list, so it scales poorly. Please use an
     * iterator remove instead.
     *
     * @param o - object equal to the one being deleted
     * @return deleted object, or null if no object was found
     */
    public Object remove(Object o) {
        ConcurrentIterator it = iterator();
        while (true) {
            Node n = (Node)it.nextElement();
            if (n == null) return null;
            if (n.o.equals(o)) {
                it.remove();
                return n.o;
            }
        }
    }
    
    public ConcurrentIterator iterator() {
        return new Itr();
    }
    
    public int size() { 
        if (size<0) {
            throw new IllegalStateException("size < 0");
        } else return size; 
    }
    
    
    
}
